/*
 * colorings of characters
 * This file is #included by regcomp.c.
 *
 * Copyright (c) 1998, 1999 Henry Spencer.	All rights reserved.
 *
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them.
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * src/common/backend/regex/regc_color.c
 *
 *
 * Note that there are some incestuous relationships between this code and
 * NFA arc maintenance, which perhaps ought to be cleaned up sometime.
 */

#define CISERR() VISERR(cm->v)
#define CERR(e) VERR(cm->v, (e))

/*
 * initcm - set up new colormap
 */
static void initcm(struct vars* v, struct colormap* cm)
{
    int i;
    int j;
    union tree* t = NULL;
    union tree* nextt = NULL;
    struct colordesc* cd = NULL;

    cm->magic = CMMAGIC;
    cm->v = v;

    cm->ncds = NINLINECDS;
    cm->cd = cm->cdspace;
    cm->max = 0;
    cm->free = 0;

    cd = cm->cd; /* cm->cd[WHITE] */
    cd->sub = NOSUB;
    cd->arcs = NULL;
    cd->firstchr = CHR_MIN;
    cd->nchrs = CHR_MAX - CHR_MIN + 1;
    cd->flags = 0;

    /* upper levels of tree */
    for (t = &cm->tree[0], j = NBYTS - 1; j > 0; t = nextt, j--) {
        nextt = t + 1;
        for (i = BYTTAB - 1; i >= 0; i--)
            t->tptr[i] = nextt;
    }
    /* bottom level is solid white */
    t = &cm->tree[NBYTS - 1];
    for (i = BYTTAB - 1; i >= 0; i--)
        t->tcolor[i] = WHITE;
    cd->block = t;
}

/*
 * freecm - free dynamically-allocated things in a colormap
 */
static void freecm(struct colormap* cm)
{
    size_t i;
    union tree* cb = NULL;

    cm->magic = 0;
    if (NBYTS > 1)
        cmtreefree(cm, cm->tree, 0);
    for (i = 1; i <= cm->max; i++) /* skip WHITE */
        if (!UNUSEDCOLOR(&cm->cd[i])) {
            cb = cm->cd[i].block;
            if (cb != NULL)
                FREE(cb);
        }
    if (cm->cd != cm->cdspace)
        FREE(cm->cd);
}

/*
 * cmtreefree - free a non-terminal part of a colormap tree
 */
static void cmtreefree(struct colormap* cm, union tree* tree, int level) /* level number (top == 0) of this block */
{
    int i;
    union tree* t = NULL;
    union tree* fillt = &cm->tree[level + 1];
    union tree* cb = NULL;

    Assert(level < NBYTS - 1); /* this level has pointers */
    for (i = BYTTAB - 1; i >= 0; i--) {
        t = tree->tptr[i];
        Assert(t != NULL);
        if (t != fillt) {
            if (level < NBYTS - 2) { /* more pointer blocks below */
                cmtreefree(cm, t, level + 1);
                FREE(t);
            } else { /* color block below */
                cb = cm->cd[t->tcolor[0]].block;
                if (t != cb) /* not a solid block */
                    FREE(t);
            }
        }
    }
}

/*
 * setcolor - set the color of a character in a colormap
 * return previous color
 */
static color setcolor(struct colormap* cm, chr c, pcolor co)
{
    uchr uc = c;
    int shift;
    int level;
    int b;
    int bottom;
    union tree* t = NULL;
    union tree* newt = NULL;
    union tree* fillt = NULL;
    union tree* lastt = NULL;
    union tree* cb = NULL;
    color prev;
    errno_t rc = EOK;

    Assert(cm->magic == CMMAGIC);
    if (CISERR() || co == COLORLESS)
        return COLORLESS;

    t = cm->tree;
    for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0; level++, shift -= BYTBITS) {
        b = (uc >> shift) & BYTMASK;
        lastt = t;
        t = lastt->tptr[b];
        Assert(t != NULL);
        fillt = &cm->tree[level + 1];
        bottom = (shift <= BYTBITS) ? 1 : 0;
        cb = (bottom) ? cm->cd[t->tcolor[0]].block : fillt;
        if (t == fillt || t == cb) { /* must allocate a new block */
            newt = (union tree*)MALLOC((bottom) ? sizeof(struct colors) : sizeof(struct ptrs));
            if (newt == NULL) {
                CERR(REG_ESPACE);
                return COLORLESS;
            }
            if (bottom)
                rc = memcpy_s(VS(newt->tcolor), sizeof(struct colors), VS(t->tcolor), BYTTAB * sizeof(color));
            else
                rc = memcpy_s(VS(newt->tptr), sizeof(struct ptrs), VS(t->tptr), BYTTAB * sizeof(union tree*));
            securec_check(rc, "", "");
            t = newt;
            lastt->tptr[b] = t;
        }
    }

    b = uc & BYTMASK;
    prev = t->tcolor[b];
    t->tcolor[b] = (color)co;
    return prev;
}

/*
 * maxcolor - report largest color number in use
 */
static color maxcolor(struct colormap* cm)
{
    if (CISERR())
        return COLORLESS;

    return (color)cm->max;
}

/*
 * newcolor - find a new color (must be subject of setcolor at once)
 * Beware:	may relocate the colordescs.
 * return COLORLESS for error
 */
static color newcolor(struct colormap* cm)
{
    struct colordesc* cd = NULL;
    size_t n;
    errno_t rc = EOK;

    if (CISERR())
        return COLORLESS;

    if (cm->free != 0) {
        Assert(cm->free > 0);
        Assert((size_t)cm->free < cm->ncds);
        cd = &cm->cd[cm->free];
        Assert(UNUSEDCOLOR(cd));
        Assert(cd->arcs == NULL);
        cm->free = cd->sub;
    } else if (cm->max < cm->ncds - 1) {
        cm->max++;
        cd = &cm->cd[cm->max];
    } else {
        /* oops, must allocate more */
        struct colordesc* newCd = NULL;

        n = cm->ncds * 2;
        if (cm->cd == cm->cdspace) {
            newCd = (struct colordesc*)MALLOC(n * sizeof(struct colordesc));
            if (newCd != NULL) {
                rc = memcpy_s(
                    VS(newCd), n * sizeof(struct colordesc), VS(cm->cdspace), cm->ncds * sizeof(struct colordesc));
                securec_check(rc, "", "");
            }
        } else
            newCd = (struct colordesc*)REALLOC(cm->cd, n * sizeof(struct colordesc));
        if (newCd == NULL) {
            CERR(REG_ESPACE);
            return COLORLESS;
        }
        cm->cd = newCd;
        cm->ncds = n;
        Assert(cm->max < cm->ncds - 1);
        cm->max++;
        cd = &cm->cd[cm->max];
    }

    cd->nchrs = 0;
    cd->sub = NOSUB;
    cd->arcs = NULL;
    cd->firstchr = CHR_MIN; /* in case never set otherwise */
    cd->flags = 0;
    cd->block = NULL;

    return (color)(cd - cm->cd);
}

/*
 * freecolor - free a color (must have no arcs or subcolor)
 */
static void freecolor(struct colormap* cm, pcolor co)
{
    struct colordesc* cd = &cm->cd[co];
    color pco, nco; /* for freelist scan */

    Assert(co >= 0);
    if (co == WHITE)
        return;

    Assert(cd->arcs == NULL);
    Assert(cd->sub == NOSUB);
    Assert(cd->nchrs == 0);
    cd->flags = FREECOL;
    if (cd->block != NULL) {
        FREE(cd->block);
        cd->block = NULL; /* just paranoia */
    }

    if ((size_t)co == cm->max) {
        while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
            cm->max--;
        Assert(cm->free >= 0);
        while ((size_t)cm->free > cm->max)
            cm->free = cm->cd[cm->free].sub;
        if (cm->free > 0) {
            Assert((size_t)cm->free < cm->max);
            pco = cm->free;
            nco = cm->cd[pco].sub;
            while (nco > 0)
                if ((size_t)nco > cm->max) {
                    /* take this one out of freelist */
                    nco = cm->cd[nco].sub;
                    cm->cd[pco].sub = nco;
                } else {
                    Assert((size_t)nco < cm->max);
                    pco = nco;
                    nco = cm->cd[pco].sub;
                }
        }
    } else {
        cd->sub = cm->free;
        cm->free = (color)(cd - cm->cd);
    }
}

/*
 * pseudocolor - allocate a false color, to be managed by other means
 */
static color pseudocolor(struct colormap* cm)
{
    color co;

    if (cm == NULL)
        return COLORLESS;

    co = newcolor(cm);
    if (CISERR())
        return COLORLESS;
    cm->cd[co].nchrs = 1;
    cm->cd[co].flags = PSEUDO;
    return co;
}

/*
 * subcolor - allocate a new subcolor (if necessary) to this chr
 */
static color subcolor(struct colormap* cm, chr c)
{
    color co;  /* current color of c */
    color sco; /* new subcolor */

    if (cm == NULL)
        return COLORLESS;

    co = GETCOLOR(cm, c);
    sco = newsub(cm, co);
    if (CISERR())
        return COLORLESS;
    Assert(sco != COLORLESS);

    if (co == sco) /* already in an open subcolor */
        return co; /* rest is redundant */
    cm->cd[co].nchrs--;
    if (cm->cd[sco].nchrs == 0)
        cm->cd[sco].firstchr = c;
    cm->cd[sco].nchrs++;
    (void)setcolor(cm, c, sco);
    return sco;
}

/*
 * newsub - allocate a new subcolor (if necessary) for a color
 */
static color newsub(struct colormap* cm, pcolor co)
{
    color sco; /* new subcolor */

    if (cm == NULL)
        return COLORLESS;

    sco = cm->cd[co].sub;
    if (sco == NOSUB) {            /* color has no open subcolor */
        if (cm->cd[co].nchrs == 1) /* optimization */
            return co;
        sco = newcolor(cm); /* must create subcolor */
        if (sco == COLORLESS) {
            Assert(CISERR());
            return COLORLESS;
        }
        cm->cd[co].sub = sco;
        cm->cd[sco].sub = sco; /* open subcolor points to self */
    }
    Assert(sco != NOSUB);

    return sco;
}

/*
 * subrange - allocate new subcolors to this range of chrs, fill in arcs
 */
static void subrange(struct vars* v, chr from, chr to, struct state* lp, struct state* rp)
{
    uchr uf;
    int i;

    Assert(from <= to);

    /* first, align "from" on a tree-block boundary */
    uf = (uchr)from;
    i = (int)(((uf + BYTTAB - 1) & (uchr)~BYTMASK) - uf);
    for (; from <= to && i > 0; i--, from++)
        newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
    if (from > to) /* didn't reach a boundary */
        return;

    /* deal with whole blocks */
    for (; to - from >= BYTTAB; from += BYTTAB)
        subblock(v, from, lp, rp);

    /* clean up any remaining partial table */
    for (; from <= to; from++)
        newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
}

/*
 * subblock - allocate new subcolors for one tree block of chrs, fill in arcs
 *
 * Note: subcolors that are created during execution of this function
 * will not be given a useful value of firstchr; it'll be left as CHR_MIN.
 * For the current usage of firstchr in pg_regprefix, this does not matter
 * because such subcolors won't occur in the common prefix of a regex.
 */
static void subblock(struct vars* v, chr start, /* first of BYTTAB chrs */
    struct state* lp, struct state* rp)
{
    uchr uc = start;
    struct colormap* cm = v->cm;
    int shift;
    int level;
    int i;
    int b;
    union tree* t = NULL;
    union tree* cb = NULL;
    union tree* fillt = NULL;
    union tree* lastt = NULL;
    int previ;
    int ndone;
    color co;
    color sco;
    errno_t rc = EOK;

    Assert((uc % BYTTAB) == 0);

    /* find its color block, making new pointer blocks as needed */
    t = cm->tree;
    fillt = NULL;
    for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0; level++, shift -= BYTBITS) {
        b = (uc >> shift) & BYTMASK;
        lastt = t;
        t = lastt->tptr[b];
        Assert(t != NULL);
        fillt = &cm->tree[level + 1];
        if (t == fillt && shift > BYTBITS) { /* need new ptr block */
            t = (union tree*)MALLOC(sizeof(struct ptrs));
            if (t == NULL) {
                CERR(REG_ESPACE);
                return;
            }
            rc = memcpy_s(VS(t->tptr), sizeof(struct ptrs), VS(fillt->tptr), BYTTAB * sizeof(union tree*));
            securec_check(rc, "", "");
            lastt->tptr[b] = t;
        }
    }

    /* special cases:  fill block or solid block */
    co = t->tcolor[0];
    cb = cm->cd[co].block;
    if (t == fillt || t == cb) {
        /* either way, we want a subcolor solid block */
        sco = newsub(cm, co);
        t = cm->cd[sco].block;
        if (t == NULL) { /* must set it up */
            t = (union tree*)MALLOC(sizeof(struct colors));
            if (t == NULL) {
                CERR(REG_ESPACE);
                return;
            }
            for (i = 0; i < BYTTAB; i++)
                t->tcolor[i] = sco;
            cm->cd[sco].block = t;
        }
        /* find loop must have run at least once */
        lastt->tptr[b] = t;
        newarc(v->nfa, PLAIN, sco, lp, rp);
        cm->cd[co].nchrs -= BYTTAB;
        cm->cd[sco].nchrs += BYTTAB;
        return;
    }

    /* general case, a mixed block to be altered */
    i = 0;
    while (i < BYTTAB) {
        co = t->tcolor[i];
        sco = newsub(cm, co);
        newarc(v->nfa, PLAIN, sco, lp, rp);
        previ = i;
        do {
            t->tcolor[i++] = sco;
        } while (i < BYTTAB && t->tcolor[i] == co);
        ndone = i - previ;
        cm->cd[co].nchrs -= ndone;
        cm->cd[sco].nchrs += ndone;
    }
}

/*
 * okcolors - promote subcolors to full colors
 */
static void okcolors(struct nfa* nfa, struct colormap* cm)
{
    struct colordesc* cd = NULL;
    struct colordesc* end = CDEND(cm);
    struct colordesc* scd = NULL;
    struct arc* a = NULL;
    color co;
    color sco;

    for (cd = cm->cd, co = 0; cd < end; cd++, co++) {
        sco = cd->sub;
        if (UNUSEDCOLOR(cd) || sco == NOSUB) {
            /* has no subcolor, no further action */
        } else if (sco == co) {
            /* is subcolor, let parent deal with it */
        } else if (cd->nchrs == 0) {
            /* parent empty, its arcs change color to subcolor */
            cd->sub = NOSUB;
            scd = &cm->cd[sco];
            Assert(scd->nchrs > 0);
            Assert(scd->sub == sco);
            scd->sub = NOSUB;
            while ((a = cd->arcs) != NULL) {
                Assert(a->co == co);
                uncolorchain(cm, a);
                a->co = sco;
                colorchain(cm, a);
            }
            freecolor(cm, co);
        } else {
            /* parent's arcs must gain parallel subcolor arcs */
            cd->sub = NOSUB;
            scd = &cm->cd[sco];
            Assert(scd->nchrs > 0);
            Assert(scd->sub == sco);
            scd->sub = NOSUB;
            for (a = cd->arcs; a != NULL; a = a->colorchain) {
                Assert(a->co == co);
                newarc(nfa, a->type, sco, a->from, a->to);
            }
        }
    }
}

/*
 * colorchain - add this arc to the color chain of its color
 */
static void colorchain(struct colormap* cm, struct arc* a)
{
    struct colordesc* cd = &cm->cd[a->co];

    if (cd->arcs != NULL)
        cd->arcs->colorchainRev = a;
    a->colorchain = cd->arcs;
    a->colorchainRev = NULL;
    cd->arcs = a;
}

/*
 * uncolorchain - delete this arc from the color chain of its color
 */
static void uncolorchain(struct colormap* cm, struct arc* a)
{
    struct colordesc* cd = &cm->cd[a->co];
    struct arc* aa = a->colorchainRev;

    if (aa == NULL) {
        Assert(cd->arcs == a);
        cd->arcs = a->colorchain;
    } else {
        Assert(aa->colorchain == a);
        aa->colorchain = a->colorchain;
    }
    if (a->colorchain != NULL)
        a->colorchain->colorchainRev = aa;
    a->colorchain = NULL; /* paranoia */
    a->colorchainRev = NULL;
}

/*
 * rainbow - add arcs of all full colors (but one) between specified states
 */
static void rainbow(struct nfa* nfa, struct colormap* cm, int type, pcolor but, /* COLORLESS if no exceptions */
    struct state* from, struct state* to)
{
    struct colordesc* cd = NULL;
    struct colordesc* end = CDEND(cm);
    color co;

    for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
        if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but && !(cd->flags & PSEUDO))
            newarc(nfa, type, co, from, to);
}

/*
 * colorcomplement - add arcs of complementary colors
 *
 * The calling sequence ought to be reconciled with cloneouts().
 * of: complements of this guy's PLAIN outarcs
 */
static void colorcomplement(struct nfa* nfa, struct colormap* cm, int type, struct state* of,
    struct state* from, struct state* to)
{
    struct colordesc* cd = NULL;
    struct colordesc* end = CDEND(cm);
    color co;

    Assert(of != from);
    for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
        if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
            if (findarc(of, PLAIN, co) == NULL)
                newarc(nfa, type, co, from, to);
}

#ifdef REG_DEBUG

/*
 * dumpcolors - debugging output
 */
static void dumpcolors(struct colormap* cm, FILE* f)
{
    struct colordesc* cd = NULL;
    struct colordesc* end = NULL;
    color co;
    chr c;
    char* has = NULL;

    fprintf(f, "max %ld\n", (long)cm->max);
    if (NBYTS > 1)
        fillcheck(cm, cm->tree, 0, f);
    end = CDEND(cm);
    for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
        if (!UNUSEDCOLOR(cd)) {
            Assert(cd->nchrs > 0);
            has = (cd->block != NULL) ? "#" : "";
            if (cd->flags & PSEUDO)
                fprintf(f, "#%2ld%s(ps): ", (long)co, has);
            else
                fprintf(f, "#%2ld%s(%2d): ", (long)co, has, cd->nchrs);

            /*
             * Unfortunately, it's hard to do this next bit more efficiently.
             *
             * Spencer's original coding has the loop iterating from CHR_MIN
             * to CHR_MAX, but that's utterly unusable for 32-bit chr. For
             * debugging purposes it seems fine to print only chr codes up to
             * 1000 or so.
             */
            for (c = CHR_MIN; c < 1000; c++) {
                if (GETCOLOR(cm, c) == co) {
                    dumpchr(c, f);
                }
            }
            fprintf(f, "\n");
        }
}

/*
 * fillcheck - check proper filling of a tree
 */
static void fillcheck(struct colormap* cm, union tree* tree, int level, /* level number (top == 0) of this block */
    FILE* f)
{
    int i;
    union tree* t = NULL;
    union tree* fillt = &cm->tree[level + 1];

    Assert(level < NBYTS - 1); /* this level has pointers */
    for (i = BYTTAB - 1; i >= 0; i--) {
        t = tree->tptr[i];
        if (t == NULL)
            fprintf(f, "NULL found in filled tree!\n");
        else if (t == fillt) {
        } else if (level < NBYTS - 2) /* more pointer blocks below */
            fillcheck(cm, t, level + 1, f);
    }
}

/*
 * dumpchr - print a chr
 *
 * Kind of char-centric but works well enough for debug use.
 */
static void dumpchr(chr c, FILE* f)
{
    if (c == '\\')
        fprintf(f, "\\\\");
    else if (c > ' ' && c <= '~')
        putc((char)c, f);
    else
        fprintf(f, "\\u%04lx", (long)c);
}

#endif /* REG_DEBUG */

